# 0-1背包问题
def knapsack(W, N, wt, val):
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]  # 对于前n个物体，当前背包容量为w时，可以装入物体的最大价值

    for n in range(1, N+1):
        for w in range(1, W+1):
            if w-wt[n-1] < 0:  # 不能装进背包
                dp[n][w] = dp[n-1][w]

            else:
                dp[n][w] = max(
                    dp[n-1][w],  # 不装入背包
                    dp[n-1][w-wt[n-1]] + val[n-1]  # 装入背包
                )

    return dp[N][W]

print("获得的最大价值为 {}".format(knapsack(4, 3, [2, 1, 3], [4, 2, 3])))

# L416分割等和子集问题
def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0: return False

    # 转化为0-1背包问题
    N = len(nums)
    W = int(total / 2)
    dp = [[False for _ in range(W+1)] for _ in range(N+1)]  # 前n个物品，当前背包容量为w

    # base case
    for k in range(N+1):
        dp[k][0] = True

    for n in range(1, N+1):
        for w in range(1, W+1):
            if w-nums[n-1] < 0:  # 无法装下了
                dp[n][w] = dp[n-1][w]
            else:
                dp[n][w] = dp[n-1][w] or dp[n-1][w-nums[n-1]]

    return dp[N][W]


nums = [1, 2, 11, 5]
print("{} 能否分割为和相等的子集？{}".format(nums, canPartition(nums)))

# L518：零钱兑换
def change(amount, coins):
    N = len(coins)
    W = amount

    # 用前n个零钱，凑出当前金额为w 共有dp[n][w]中凑法
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    for k in range(N+1):
        dp[k][0] = 1

    for n in range(1, N+1):
        for w in range(1, W+1):
            if w - coins[n-1] < 0:  #
                dp[n][w] = dp[n-1][w]
            else:
                dp[n][w] = dp[n-1][w] + dp[n][w-coins[n-1]]  # 注意这里不是dp[n-1][w-coins[n-1]]，因为是无限数量

    return dp[N][W]

amount = 11
coins = [1, 2, 3, 4, 5]
print("利用coins={}, 凑成amount={}, 共有{}种凑法".format(coins, amount, change(amount, coins)))
